// Package coding_round_1 day_01_stack_mid_range_tree
// @Title coding_round_1
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/2 11:40
// @Create  2021/9/2 11:40
package coding_round_1

// MidRangeStack  使用栈实现二叉树的  中序遍历
func MidRangeStack(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	ans := make([]int, 0)
	// 第一步 创建一个空栈
	var stack = make([]*TreeNode, 0)
	//var stack = []*TreeNode{root}
	curNode := root
	for len(stack) > 0 || curNode != nil {
		// 如果当前节点有左子树，就一直压左节点到最左边
		if curNode != nil {
			stack = append(stack, curNode)
			curNode = curNode.Left
		} else {
			// 否则就从栈中弹出一个元素，
			curNode = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			ans = append(ans, curNode.Val)
			curNode = curNode.Right
		}
	}
	return ans
}
